Например, Бобцов

ПРИМЕНЕНИЕ МЕТОДА УРОВНЕЙ ПРИСПОСОБЛЕННОСТИ ДЛЯ АНАЛИЗА ДИНАМИКИ РАБОТЫ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ

Аннотация:

Предмет исследования. В области теории эволюционных алгоритмов в настоящее время становится акту- альным анализ не только времени их работы, но и динамики. Двумя наиболее распространенными методами анализа динамики являются: анализ достижимой приспособленности при ограничении на время работы (fixed- budget analysis) и анализ времени работы, необходимого для достижения заданной цели (fixed-target analysis). До сих пор теоретические исследования систематически выполнялись только для первого из них. Настоящая работа направлена на устранение этого недостатка. Метод. Доказана теорема о том, что если для комбинации эволюционного алгоритма и задачи оптимизации ранее были доказаны оценки времени работы с помощью так называемого метода уровней приспособленности, то из необходимых для этого предпосылок автоматически следуют оценки динамики работы эволюционного алгоритма для рассматриваемой задачи. Основные результаты. В результате применения данной теоремы получены верхние оценки времени работы, которое необходимо для достижения заданной цели следующих пар алгоритмов и задач: эволюционные алгоритмы семейства (1 + 1) на задачах LeadingOnes и OneMax, эволюционный алгоритм (μ + 1) на задаче OneMax. Данные оценки повторяют или уточняют существующие результаты, но получают их существенно более простым способом. Практическая значимость. Результаты работы позволяют упростить получение оценок динамики работы эволюционных алгоритмов. Подобные оценки являются более содержательным критерием для выбора эволюционного алгоритма с целью решения практической задачи, чем оценка времени нахождения оптимального решения, так как последнее на практике чаще всего недостижимо.

Ключевые слова:

Постоянный URL

Статьи в номере

Содержание © 1993–2024 Университет ИТМО
Разработка © 2015 Университет ИТМО